/**
 * 子序列最大和
 */
public class MaxSubArray {
    public static void main(String[] args) {
        int nums[] = {1};
        System.out.println(solution1(nums));
    }

    /**
     * 动态规划
     * @param nums
     * @return
     */
    public static  int solution(int nums[]){
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int result = dp[0];
        int size = nums.length;
        for(int i = 1 ; i < size ;i++){
            // 动态递归方式
            dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
            // 保存最大值
            if (dp[i] > result) result = dp[i];
        }
        return result;
    }

    public static int solution1(int nums[]){
       int result = nums[0];
       int size = nums.length;
       int sum = result;
       for (int i = 1 ; i < size ; i++){
          sum = Math.max(sum+nums[i],nums[i]);
          if (sum > result) result = sum;
       }
       return result;
    }

}
